\chapter{Approximate Revenue via simple auction mechanisms with multiple items}
In this chapter, we will introduce two simple auction mechanisms that approximate optimal revenue. The game setting is to obtain approximate maximal revenue when there is only one seller selling $k$ different items. The two mechanisms introduced here are to sell the items separately, and to sell the items as a whole bundle. Here we will be more focused on the revenue obtained by these two simple mechanisms compared with the optimal auction mechanism. The comparison will be based on the fraction of revenue that these two simple auction mechanisms obtained compared with optimal auction mechanism.
\section{Notations and Preliminaries}
In this setting, the auctioneer possesses $k \geq 1$ items, which are worth nothing to him, as well as no manufacturing cost counts. For the simple case, we discuss the case that there is only one bidder. One thing that should be clarified is that the auctioneer has no private information and commits in this mechanism, while the bidder has a private valuation for the $k$ items. For the outcome, we should specify an allocation scheme that tells the probability of obtaining each of the $k$ items, along with an expected payment the auctioneer obtain from the bidder. We can build the following basic definition for better characterization about what we care about in this auction design game.
\begin{itemize}
\item Bidder's valuation: We let $x := (x_1, \ldots, x_k)$ where $x_i \geq 0$ represents the valuation of the buyer for item $i$.
\item Allocation: We let $q := (q_1, \ldots, q_k) \in [0,1]^k$ to be the allocation which for all $i$, $q_i$ is a function taking valuation $x$ as input and counts the probability that item $i$ is allocated to this bidder.
\item Auctioneer's revenue: We let $s := s(x)$ to be the expected payment that the auctioneer obtains from the bidder when the bidder's valuation is $x$.
\item Bidder's utility: We let $b := b(x)$ to be the utility function of the bidder when the valuation of this bidder is $x$. To present in a more formal way, we have $b(x) = x \cdot q(x) - s(x)$, where $\cdot$ means inner product.

For these mechanisms, we will have several restriction, which is actually natural in social marketing situations. Here are the requirements:
\begin{itemize}
\item No positive transfers(NPT): $\forall x, s(x) \geq 0$
\item Individually Rational(IR): $\forall x, b(x) \geq 0$
\item Incentive Compatible(IC): $\forall x, x'$: we have $\sum_i x_i q_i(x) - s(x) \geq \sum_i x_i q_i(x') - s(x')$ 
\end{itemize}
The idea of NPT and IR is clear: for an auctioneer, he will not lose any of his goods while giving out the money, which indicates NPT; for a bidder, he does not have the motivation to obtain an item with a price higher than his valuation to this item, which provides IR. For IC, this definition actually represents the idea that for a buyer with valuation $x$, he is playing a strategically in the mechanism. In other words, this restriction has the same idea with the dominant strategy as well as Bayes-Nash imiiplementation notions.
\end{itemize}
To see more clearly what the IC condition brings to the mechanism, we introduce the following two conditions which are equivalent to incentive compatible, via the following lemma.
\begin{lem}\label{lem1}
For a mechanism with $b(x) = x \cdot q(x) - s(x)$, the following two conditions are equivalent with incentive compatible:
\begin{enumerate}
\item The allocation function $q$ is weakly monotone on $x$, along with the payment to the auctioneer satisfies $\forall x, x', x \cdot (q(x) - q(x')) \geq s(x) - s(x') \geq x' \cdot (q(x) - q(x'))$
\item The bidder's utility function $b$ is a convex function of $x$, together with the condition stands that for all $x$, the allocation $q(x)$ is a subgradient of $b$ at $x$. That means $b(x') - b(x) \geq q(x)\cdot (x'-x)$, along with $q_i(x) = \frac{\partial b(x)}{\partial x_i}$
\end{enumerate}
\end{lem}
\begin{proof}
\begin{enumerate}
\item Sufficiency: From 1, we have $x \cdot (q(x) - q(x')) \geq s(x) - s(x')$, which actually is incentive compatible. Thus sufficiency is proved.

Necessity: From IC, we have $x \cdot (q(x) - q(x')) \geq s(x) - s(x')$, and change the order of $x$ and $x'$ in IC representation, we can obtain $s(x) - s(x') \geq x' \cdot (q(x) - q(x'))$, Thus necessity is proved.
\item Sufficiency: From 2, together with the definition of bidder's utility, we have
\begin{equation}
\begin{aligned}
0 &\leq b(x') - b(x) - q(x) \cdot (x' - x) \\
&= x'\cdot q(x') - s(x') - x \cdot q(x) + s(x) + x \cdot q(x) - x' \cdot q(x)\\
&= x'\cdot (q(x')- q(x))- (s(x') - s(x))
\end{aligned}
\end{equation}
From the previous proof we can see that this is equivalent to the definition of incentive compatible.

Necessity: As the sufficiency part indicates, from IC we can get $b(x') - b(x) \geq q(x)\cdot (x'-x)$, this implies that the bidder's utility function is convex on $x$, and the allocation function $q$ is a subgradient of $b$ at $x$.
\end{enumerate}
\end{proof}
From this sets of equivalent conditions, we can see that for any convex function $b$, if $0 \leq \frac{\partial b(x)}{\partial x_i} \leq 1$ for all $i$, then this function $b$ defines an incentive compatible mechanism by setting allocations $q_i = \frac{\partial b(x)}{\partial x_i}$ and $s(x) = x\cdot q(x) - b(x)$.

When bidder's valuation for all $k$ items are respect to the joint cumulative distribution function $\mathcal{F}$ on $R_+$, the expected revenue of the mechanism given by $b$ is:
\begin{equation}
R(b;\mathcal{F}) = \mathbb{E}_{x\sim \mathcal{F}}(s(x)) = \int \cdots \int (\sum_{i = 1}^k x_i \frac{\partial b(x)}{\partial x_i} - b(x)) d \mathcal{F}(x_1, \ldots, x_k).
\end{equation}
Below we will introduce the notation of optimal auction and two simple approximate auctions we study.

For a joint cumulative distribution function $\mathcal{F}$ described above, we have:
\begin{itemize}
\item $REV(\mathcal{F})$: This means the revenue obtained from the optimal auction which maximize the revenue.
\item $BREV(\mathcal{F})$: This means the maximal revenue obtained by selling the $k$ items as a bundle.
\item $SREV(\mathcal{F})$: This means the maximal revenue obtained by selling the $k$ items separately.
\end{itemize}
Thus, for special case $k = 1$, we have
\begin{equation}
REV(F) = SREV(F) = BREV(F) = \sup_{p \geq 0} p \cdot \mathbb{P}(X\geq p)
\end{equation}
Which is the Myerson's Characterization.

For this part, we assume that the valuation of the $k$ items for the bidder are independent, and thus we have $\mathcal{F} = F_1 \times \cdots \times F_k$, and for the bundle and separate mechanism, we have:
\begin{equation}
\begin{aligned}
BREV(\mathcal{F})  &=  REV(F_1 \ast \cdots \ast F_k)\\
SREV(\mathcal{F})  &=  REV(F_1) + \cdots + REV(F_k)
\end{aligned}
\end{equation}
\section{A first view of separate and bundled auction mechanism}
For selling multiple items, for example two items, it seems at first glance that since the two items are completely independent from each other, the best we can do is to sell them separately in the optimal way, or in other words, using separate mechanisms, and thus extract exactly twice the revenue we would make from a single item. This turns out to be false. Here are two examples that illustrate respectively that in different cases, either may be better.

The first example is to consider the distribution taking values of $1$ and $2$, each with probability $\frac{1}{2}$. Let us first look at selling a single item optimally: the seller can either choose to price it at $1$, selling always and getting a revenue of $1$, or choose to price the item at $2$, selling it with probability $\frac{1}{2}$, still obtaining an expected revenue of $1$, and so the optimal revenue for a single item is $1$. Now consider the following mechanism for selling both items: bundle them together, and sell the bundle for price 3. The probability that the sum of the buyer's values for the two items is at least $3$ is $\frac{3}{4}$, and so the revenue is $3\cdot \frac{3}{4} = 2.25$ which is larger than $2$, which is the revenue obtained by selling them separately.

The second example is to consider the distribution taking values $0$ and $1$, each with probability $\frac{1}{2}$, selling the bundle can yield at most a revenue of $\frac{3}{4}$, and this is less than twice the
single-item revenue of $\frac{1}{2}$.

In some other cases neither selling separately nor bundling is optimal. For the distribution that takes values $0$, $1$ and $2$, each with probability $\frac{1}{3}$, the unique optimal auction turns out to offer to the buyer the choice between any single item at price $2$, and the bundle of both items at a ''discount'' price of $3$. This auction gets revenue of $\frac{13}{9}$ revenue, which is larger than the revenue of $\frac{4}{3}$ obtained from either selling the two items separately, or from selling them as a single bundle. A similar
situation happens for the uniform distribution on $[0,1]$, for which neither bundling nor selling separately is optimal\cite{manelli2006bundling}
\section{Approximation in two items case: lower bounds}
In this section, we will provide a lower bound for selling two items using the two simple auctions: separate and bundle, which were both formally defined in the above section. This lower bound is defined as the fraction that these simple auction mechanisms obtains from the optimal auction mechanisms.

Also, we will classify and discuss the situations that the distributions of items' valuations are identical or different, since for the former case we may prove that the simple mechanism can probably obtains a higher revenue. 
\subsection{Separate mechanism}
\subsubsection{Different distribution}
In this situation, we claim that at least half of the optimal revenue can be obtained. To prove this, let's first see the following lemmas which are useful.\\
\begin{lem}\label{lem2}
Let $X$ and $Y$ be one-dimensional independent random variable, then we have:
\begin{equation}
REV(X,Y) \leq E(Y) + REV(X)
\end{equation}
where $E(Y)$ represents the expectation of random variable $Y$.
\end{lem}
\begin{proof}
Here we build an induced mechanism to obtain the optimal revenue from $(X,Y)$. In this mechanism, we fix the value of item $Y$, and assume that this mechanism is IC and IR, but also hands out item $Y$'s value. We make a compensate for the $Y$'s value by paying back the bidder with an additional amount of money $qy$. As we can see, the revenue of this mechanism conditioned on $Y = y$ is no less than $REV(X,Y = y) - qy$. Thus we have $E_{y\sim Y}(REV(X)) \geq REV(X,Y) - E(Y)$, and the lemma is proved.
\end{proof}
Below we will use $Z$ to denote the two-dimensional random variable $(X,Y)$.
\begin{lem}\label{lem3}
Let $S$ be a subset of the domain of $Z$, then we have:
\begin{equation}
REV(\mathbbm{1}_{Z\in S} Z) \leq REV(Z)
\end{equation} 
\end{lem}
\begin{proof}
This is a special case of NPT: the left hand side obtains a fraction of revenue in an induced mechanisms selling $Z$, which is for sure less that the optimal revenue of $Z$.
\end{proof}
\begin{lem}\label{lem4}
Let $S$ and $T$ be two subsets of the domain of $Z$, such that $S\cup T$ contains the domain of $Z$, then we have:
\begin{equation}
REV(\mathbbm{1}_{Z\in S} Z) + REV(\mathbbm{1}_{Z\in T} Z) \geq REV(Z)
\end{equation} 
\end{lem}
\begin{proof}
Take the optimal mechanism for $Z$. For the domain of $Z$, we can divide it with part $S$ and $T$. For the part $S$, $REV(\mathbbm{1}_{Z\in S} Z)$ obtains no less than applying this optimal mechanism. This is so in part $T$ which contains almost complement of $S$, thus the lemma stands.
\end{proof}
\begin{lem}\label{lem5}
Let $X$ and $Y$ be one-dimensional independent random variable, $S$ be a subset of the domain of $(X,Y)$, then we have:
\begin{equation}
REV(\mathbbm{1}_{(X,Y)\in S} \cdot (X,Y)) \leq E(\mathbbm{1}_{(X,Y)\in S} Y) + REV(X)
\end{equation} 
\end{lem}
\begin{proof}
Define $S_y := \{x|(x,y) \in S\}$. Using Lemma\ref{lem2}, we can get $REV(\mathbbm{1}_{(X,Y)\in S} \cdot (X,Y)) \leq E(\mathbbm{1}_{(X,Y)\in S} Y) + E_y[REV(\mathbbm{1}_{(X,Y)\in S_y}X)]$, and from Lemma\ref{lem3}, $REV(\mathbbm{1}_{(X,Y)\in S_y}X) \leq REV(X)$ for all $y$. Thus the lemma is proved.
\end{proof}
\begin{lem}\label{lem6}
Let $X$ and $Y$ be one-dimensional independent random variables. We have:
\begin{equation}
E(\mathbbm{1}_{Y\leq X} Y) \leq REV(X)
\end{equation}
\end{lem}
\begin{proof}
The left side can be treated as a mechanism for selling $X$. Choose a random $y$ according to Y and offer this as the price. We can see that the revenue of this mechanism is $E_{y\sim Y}(y\cdot P(X\geq y)) = E(\mathbbm{1}_{Y\leq X} Y)$, which is a lower bound of $REV(X)$.
\end{proof}
Now we provide the formal formulation of this approximate lower bound with Theorem\ref{thm21}.
\begin{thm}\label{thm21}
For every two-dimensional distributions $\mathcal{F} = F_1 \times F_2$, where $F_1$ and $F_2$ are independent, we have:
\begin{equation}
SREV(\mathcal{F}) \geq \frac{1}{2} REV(\mathcal{F})
\end{equation}
\end{thm}
\begin{proof}
Apply Lemma\ref{lem4}, we can see the following equations works.
\begin{equation}
REV(X,Y) \leq REV(\mathbbm{1}_{Y\leq X}(X,Y)) + REV(\mathbbm{1}_{X\leq Y}(X,Y))
\end{equation}.
Then apply Lemma\ref{lem5} and Lemma\ref{lem6}, we can see the first term $REV(\mathbbm{1}_{Y\leq X}(X,Y))$ can be bounded by $E(\mathbbm{1}_{Y\leq X} Y) + REV(X) \leq 2REV(X)$. For the other term apply the similar method, and this theorem is proved.
\end{proof}
\subsubsection{Identical distribution}
In this situation, we claim that at least $\frac{e}{e+1}$ of the optimal revenue can be obtained. To prove this, let's first see the following lemma which is useful.
\begin{lem} \label{lem7}
Let $X$ be a one-dimensional random variable whose support is included in $[x_0, \infty)$ for some $x_0 \geq 0$, and let $b_0 \geq 0$ and $q_0 \in [0,1]$. Then the maximal revenue the seller can obtain from $X$ subject to guaranteeing to the buyer a payoff at least $b_0$ and a probability of getting the item of at least $q_0$ is:
\begin{equation}
(1-q_0)REV(X) + q_0 x_0 - b_0
\end{equation}
\end{lem}
\begin{proof}
A mechanism satisfying these constraints is plainly seen to correspond to a one-dimensional convex function $b$ with $q_0 \leq b'(x) \leq 1$ and $b(x_0) = b_0$. When $q_0 < 1$, put $\tilde{b}(x) = (b(x) - q_0(x-x_0) - b_0)/(1-q_0)$, then $\tilde{b}$ is a convex function with $\tilde{b}(x) \in [0,1]$ and $\tilde{b}(x_0) = 0$, and so $REV(F)\leq R(\tilde{b};F) = (R(b;F)-q_0 x_0+b_0)/(1-q_0)$
\end{proof}
Now we provide the formal formulation of this approximate lower bound with Theorem\ref{thm22}
\begin{thm}\label{thm22}
For every two-dimensional distributions $\mathcal{F} = F_1 \times F_2$, where $F_1$ and $F_2$ are independent, we have:
\begin{equation}
SREV(\mathcal{F}) \geq \frac{e}{e+1} REV(\mathcal{F})
\end{equation}
\end{thm}
\begin{proof}
Let $X$ and $Y$ be identical independent distribution random variables with respect to distribution function $F$. Without loss of generality we will restrict ourselves to symmetric mechanisms such that $b(x,y )  = b(y,x)$. And we denote $R = REV(X) =  REV(Y) = \sup_{t\geq 0} t \cdot \bar{F}(t)$, where $\bar{F}(t) :=  P(X \geq t) = \lim_{u\rightarrow t^+}(1-F(u))$.

Define $\phi(x) = q_1(x,x) = q_2(x,x)$ and $\Phi(x) = b(x,x)/2$, then $\Phi(x) = \int_0^x \phi(t)dt$(Here $b(0,0) = 0$ since IR and NPT stands).

We will consider the two regions $X\geq Y$ and $Y\geq X$ separately; by symmetry the expected revenue in the two regions is the same, and so it suffices to show that
\begin{equation}
E(s(X,Y)\mathbbm{1}_{X\geq Y}) \leq (1 + \frac{1}{e})R
\end{equation}
We build an induced mechanism. Fix $y$ and define a mechanism $(\tilde{q}^y, \tilde{s}^y)$ for $X$ by $\tilde{q}^y(x) = q_1(x,y)$ and $\tilde{s}^y(x) = s(x,y) - yq_2(x,y)$ for every $x$; note that the buyer's payoff is $\tilde{b}^y(x) = b(x,y)$. The mechanism $(\tilde{q}^y, \tilde{s}^y)$ is IC and IR for $X$, since $(q,s)$ was IC and IR for $(X,Y)$. Now apply the mechanism $(\tilde{q}^y, \tilde{s}^y)$ to the random variable $X$ conditioned on $[X \geq y]$, which we write $X_y$ for short. Since $X_y \geq y$ we have $\tilde{b}^y (X_y) = b(X_y, y) \geq b(y,y) = 2\Phi(y)$ and $\tilde{q}^y(X_y) = q_1(X_y, y) \geq q_1(y,y) = \phi(y)$, and apply the lemma above we can get:
\begin{equation}
E(\tilde{s}^y(X) | X \geq y) = E(\tilde{s}^y(X_y)) \leq (1-\phi(y))REV(X_y) + y\phi(y) - 2\Phi(y)
\end{equation}
Since $P(X_y \geq t) = P(X\geq t)/P(X\geq y) = \bar{F}(t) / \bar{F}(y)$ for all $t \geq y$, we get
\begin{equation}
\begin{aligned}
REV(X_y) &= \sup_{z\geq 0} z\cdot P(X_y \geq z) \\&= \sup_{z\geq y} z\cdot \bar{F}(z) / \bar{F}(y) \\&\leq \sup_{z\geq 0} z\cdot \bar{F}(z) / \bar{F}(y) \\&= R/\bar{F}(y)
\end{aligned}
\end{equation}
Multiply eq \ref{eqe1} by $P(X_y) = \bar{F}(y)$ we get:
\begin{equation}
E(\tilde{s}^y(X) \mathbbm{1}_{X\geq y}) \leq (1-\phi(y))R + (y\phi(y) - 2\Phi(y))\bar{F}(y)
\end{equation}
We take expectation on both sides, and get:
\begin{equation}\label{eqe1}
E(\tilde{s}^Y(X) \mathbbm{1}_{X\geq Y}) \leq E(1-\phi(Y))R + E((Y\phi(Y) - 2\Phi(Y))\mathbbm{1}_{X\geq Y})
\end{equation}
Since $s(x,y) = \tilde{s}^y(x) + yq_2(x,y) \leq \tilde{s}^y(x) + yq_2(x,x) = \tilde{s}^y(x) + y\phi(x)$, we finally get:
\begin{equation}\label{ege3}
\begin{aligned}
E(s(X,Y) \mathbbm{1}_{X\leq Y}) &= E(\tilde{s}^Y(X) \mathbbm{1}_{X\leq Y}) + E(Y\Phi(x)\mathbbm{1}_{X\geq Y}) \\&\leq R-RE(\phi(Y)) + E(W\mathbbm{1}_{X\geq Y})
\end{aligned}
\end{equation}
where
\begin{equation}\label{ege2}
W := Y\phi(X) + Y\phi(Y) - 2\Phi(Y).
\end{equation}
Since eq\ref{ege2} is affine in $\phi$, and $\phi$ is non-decreasing function with values in $[0,1]$. Thus, we only need to consider the extreme cases when bounding this expression.

When $\phi(x) = \mathbbm{1}_{[t,\infty)}$ we get $\Phi(x) = \max \{x-t, 0\}$ and 
\begin{equation}
W = \left\{ \begin{array}{ll}
2Y - 2(Y - t) = 2t & \textrm{if $X \geq Y \geq t$}\\
Y - 0 = Y & \textrm{if $X \geq t > Y$}\\
0 & \textrm{if $t > X \geq Y$}
\end{array} \right.
\end{equation}
Thus 
\begin{equation}
\begin{aligned}
E(\mathbbm{1}_{X\geq Y}) &= 2 t P(X\geq Y \geq t) + E(Y \mathbbm{1}_{X\geq t > Y}) \\&= t P(X\geq t)P(Y \geq t) + P(X\geq t)E(Y \mathbbm{1}_{t > Y}) \\&=  P(X\geq t) E(\min\{Y,t\}) = \bar{F}(t)E(\min\{Y,t\})
\end{aligned}
\end{equation}
Then we can rewrite eq \ref{ege3} as follows:
\begin{equation}
R - R\bar{F}(t) + \bar{F}(t)E(\min\{Y,t\}) = R + \bar{F}(t)(E(\min\{Y,t\}) - R)
\end{equation}
When $t \leq R$ we have $E(\min\{Y, t\}) \leq R$, and so
$R + \bar{F}(t)(E(\min\{Y,t\}) - R) \leq R$. When $t > R$ we have
\begin{equation}
\begin{aligned}
E(\min\{Y,t\}) &= \int_0^{\infty}P(\min\{Y, t\} \\&\geq u) du = \int_0^t P(Y \geq u)du \\&= \int_0^t \bar{F}(u) du \leq \int_0^R 1du + \int_R^t \frac{R}{u} du = R + Rlog(\frac{t}{R})
\end{aligned}
\end{equation}
Therefore in this case
\begin{equation}
\begin{aligned}
R + \bar{F}(t)(E(\min\{Y,t\}) - R) &\leq R + \frac{R}{t}(R + R\log(\frac{t}{R}) - R) \\&=  R(1+ \frac{\log \frac{t}{R}}{\frac{t}{R}})
\end{aligned}
\end{equation}
Since $\max_{\frac{t}{R}\geq 1} \frac{R}{t} \log \frac{t}{R} = \frac{1}{e}$, then we have $R + \bar{F}(t)(E(\min\{Y,t\}) - R) \leq (1 + \frac{1}{e})R$ for all $t > R$, as well as for $t \geq 0$ from the previous discussion. Thus $E(s(x,y)) \leq 2(1 + \frac{1}{e})R = (1+\frac{1}{e})SREV(F\times F)$. The theorem is finally proved.
\end{proof}
\subsection{Bundled mechanism}
\subsubsection{Different distribution}
In this situation, we claim that at least $\frac{1}{4}$ of the optimal revenue can be obtained. To prove this, let's first see the following lemma using the $\mathcal{F}$ and $F_1, F_2$ defined above.
\begin{lem}\label{lem8}
$BREV(F_1 \times F_2) \geq \frac{1}{2}SREV(F)$
\end{lem}
\begin{proof}
For every $i$ we have $REV(F_i) \leq BREV(\mathcal{F})$. Sum up all these inequalities we get this lemma.
\end{proof}
Now we provide the formal formulation of this approximate lower bound with Theorem\ref{thm23}
\begin{thm}\label{thm23}
For every two-dimensional distributions $\mathcal{F} = F_1 \times F_2$, where $F_1$ and $F_2$ are independent we have:
\begin{equation}
BREV(\mathcal{F}) \geq \frac{1}{4} REV(\mathcal{F})
\end{equation}
\end{thm}
\begin{proof}
With Theorem\ref{thm21} and Lemma\ref{lem8}, we have:
\begin{equation}
\begin{aligned}
BREV(\mathcal{F}) &\geq \frac{1}{2} SREV(\mathcal{F})\\ &\geq \frac{1}{2} \times \frac{1}{2} REV(\mathcal{F})\\ &= \frac{1}{4} REV(\mathcal{F})
\end{aligned}
\end{equation}
\end{proof}
\subsubsection{Identical distribution}
In this situation, we claim that at least $\frac{1}{4}$ of the optimal revenue can be obtained. To prove this, let's first see the following lemma which is useful.
\begin{lem}\label{lem9}
For every one-dimensional distribution F, we have:$BREV(F \times F) \geq \frac{2}{3} \cdot SREV(F \times F)$
\end{lem}
\begin{proof}
We denote $p$ as the optimal Myerson's price when the valuation distribution is $F$, and $q$ be the probability that the bidder will buy at price $p$. We can discuss the interval of $q$.
\begin{enumerate}
\item $q \leq \frac{2}{3}$. In this case we can set the bundling auction price at $p$. Thus, the probability that the bidder will pay is at least $1-(1-q)^2 = q(2-q) \geq \frac{4}{3} q$, and the revenue will be at least $4q/3 \cdot p = \frac{4}{3} REV(F) = \frac{2}{3} SREV(F \times F)$
\item $q \geq \frac{2}{3}$. In this case we can set the bundling auction price at $2p$. Thus, the probability that the bidder will pay is at least $2q^2p \geq \frac{4}{3}qp = \frac{2}{3} SREV(F \times F)$
\end{enumerate}
\end{proof}
Now we provide the formal formulation of this approximate lower bound with Theorem\ref{thm24}
\begin{thm}\label{thm24}
For every two-dimensional distributions $\mathcal{F} = F_1 \times F_2$, where $F_1$ and $F_2$ are independent, we have:
\begin{equation}
SREV(\mathcal{F}) \geq \frac{2}{3} \cdot \frac{e}{e+1} REV(\mathcal{F})
\end{equation}
\end{thm}
\begin{proof}
With Theorem\ref{thm22} and Lemma\ref{lem8}, we have:
\begin{equation}
\begin{aligned}
BREV(\mathcal{F}) &\geq \frac{2}{3} SREV(\mathcal{F})\\ &\geq \frac{2}{3} \times \frac{e}{e+1} REV(\mathcal{F})\\ &= \frac{2}{3} \cdot \frac{e}{e+1} REV(\mathcal{F})
\end{aligned}
\end{equation}
\end{proof}
\section{Approximation in more than two items case: lower bounds}
We first introduce a few more lemmas, which will be used in proving the lower bounds.
\begin{lem}\label{lem10}
Let $X$ and $Y$ be multi-dimensional random variables. If $X$ and $Y$ are independent, then 
\begin{equation}
VAL(\mathbbm{1}_{\sum_j Y_j \leq \sum_i X_i} Y) \leq BREV(X)
\end{equation}
\end{lem}
\begin{proof}
Apply Lemma\ref{lem6} to the one-dimensional random variables $\sum_i X_i$ and $\sum_j Y_j$, and recall that $REV(\sum_i X_i) = BREV(X)$
\end{proof}
\begin{lem}\label{lem11}
Let $X$ and $Y$ be multi-dimensional random variables. If $X$ and $Y$ are independent, then:
\begin{equation}
REV(X,Y) \leq REV(X) + REV(Y) + BREV(X) + BREV(Y)
\end{equation}
\end{lem}
\begin{proof}
We can cut the valuation space by $REV(X,Y) \leq REV(\mathbbm{1}_{\sum_j Y_j \leq \sum_i X_i} \cdot (X,Y)) + REV(\mathbbm{1}_{\sum_i X_i \leq \sum_j Y_j} \cdot (X,Y))$.  The first term can be bounded by $E(\mathbbm{1}_{\sum_j Y_j \leq \sum_i X_i} Y) + REV(X) \leq BREV(X) + REV(X)$, using Lemma\ref{lem5} and Lemma\ref{lem10}. For the other term apply the similar inequality and this lemma is proved.
\end{proof}
\subsection{Separate mechanism}
Here we provide a proof for a lower bound of $\Omega(\frac{1}{log^2 k})$ fraction of the optimal revenue, which is stated below:
\begin{proof}
Assume that $k \leq 2$ is a power of $2$, and we will prove by induction that $REV(F_1 \times \cdots \times F_k) \leq c log^2 (2k) \sum_{i = 1}^{k} REV(F_i)$, where $c$ is a constant. By applying Lemma\ref{lem11} to $(F_1 \times \cdots \times F_{k/2})\times (F_{k/2+1} \times \cdots \times F_{k})$ we get:
\begin{equation}
\begin{aligned}
REV(F_1 \times \cdots \times F_{k}) &\leq BREV(F_1 \times \cdots \times F_{k/2}) + BREV(F_{k/2+1} \times \cdots \times F_{k}) \\&+ REV(F_1 \times \cdots \times F_{k/2}) + REV(F_{k/2+1} \times \cdots \times F_{k})
\end{aligned}
\end{equation}
for the BREV terms, their sum is bounded by $c log k\sum_{i = 1}^k REV(F_i)$. Apply the induction hypothesis on both REV terms, their sum is bounded by $c log^2 k \sum_{i = 1}^k REV(F_i)$. Now $log k + log^2 k \leq log^2(2k)$, and so the coefficient of each $REV(F_i) $ is at most $c log^2(2k)$ as required.

When $k \in (2^{m-1}, 2^m)$ we can pad to $2^m$ with items that have value identically zero. This is at most doubles $k$.
\end{proof}
\subsection{Bundled mechanism}
Here we can obtain a fraction of $\Omega(\frac{1}{k})$ of the optimal mechanism for the bundled case. 
\begin{proof}
For $k$ a power of two, we can prove by induction that $REV(F_1 \times \cdots \times F_k) \leq (3k -2)BREV(F_1 \times \cdots \times F_k)$, just as it happens in the previous proof. One thing to note is that we use the fact that the bundled revenue from a subset of the items is at most the bundled revenue from all of them. For $k$ not a power of two we can pad to the next power of $2$ with items that have value identically zero, which at most doubles $k$.
\end{proof}
For identical distributed items, we can prove a better lower bound $\Omega(\frac{1}{log k})$. Here is the proof.
\begin{proof}
For $k \geq 2$ a power of two we apply Lemma\ref{lem11} recursively to obtain: $REV(F^{\times k}) \leq 2BREV(F^{\times(k/2)}) + 4 BREV(F^{\times (k/4)}) + \cdots + (k/2)BREV(F^{\times 2}) + k BREV(F) + k REV(F)$. Each of the $log_2 k + 1$  terms in this sum is on the form $(k/m)BREV(F^{\times m}) = (k/m) REV(F^{\ast m})$ and is thus bounded from above, by $4 REV(F^{\ast k}) = 4 BREV(F^{\times k})$. Altogether we have $REV(F^{\times k}) \leq 4(log_2 k + 1) BREV(F^{\times k})$.

When $k \in (2^{m-1}, 2^m)$ we have $REV(F^{\times k}) \leq REV(F^{\times 2^m}) \leq 4(log_2 2^m + 1)BREV(F^{\times 2^m}) \leq 4(log_2 k + 2)\cdot 2\cdot 1.3\cdot BREV(F^{\times 2^{m-1}}) \leq 4(log_2 k + 2) \cdot 2 \cdot 1.3 \cdot BREV(F^{\times k})$.
\end{proof}
\section{Approximation in multi-items case: upper bounds}
In this section, we will provide upper bounds for all multi-item cases. Here upper bound does not has it's real meaning, but finding an example describe the upper bound of the lower bound of these two mechanisms.

To begin with, a special distribution called Equal Revenue(ER) distribution will be first introduced as follows:
this distribution has a density function $f(x) = x^{-2}$ for $x \geq 1$, and for $x \leq 1$ we have $f(x) = 0$. From the Myerson's characterization, we can conclude that $REV(ER) = 1$, while its expected value is infinite. 

Now we will start with our examples:
\subsection{Separate mechanism}
\subsubsection{Two items}
Let $\mathcal{F} = ER \times ER$, We can calculate $REV(\mathcal{F}) = BREV(\mathcal{F}) = 2.5569$, and $SREV(\mathcal{F}) = 2$. So in this example we obtain the upper bound $2/2.5569 \approx 0.78$
This example stands for all two item cases where the distribution only needs to be independent.
\subsubsection{More than two items}
Here we provide an example that $\frac{1}{\log k}$ fraction can be reached.

We still use the ER distribution, and prove that $BREV(ER^{\times k}) \leq c_1 k logk$, here $c_1 = \frac{1}{4}$.

Let $X$ be a random variable with distribution ER; for $M \geq 1$ let $X^M = \min\{X,M\}$ be $X$ truncate at $M$. It is immediate to compute $E(X^M) = \log M + 1$ and $Var(X^M)\leq 2M$. Let $X_1, \ldots, X_k$ be identical independent ER distribution. For every $p, M > 0$ we have $REV(\sum_i X_i) \geq p\cdot P(\sum_i X_i \geq p)\geq p \cdot P(\sum_i X_i^M \geq p)$.

When $M = k\log k$ and $p = \frac{k \log k}{2}$ we get $(k E(X^M ) -p) /\sqrt{kVar(X^M)} \geq \sqrt{\log k / 8}$, so $p$ is at least $\sqrt{\log k/8}$ standard deviations below the mean of $\sum_{i=1}^k X_i^M$. Therefore, by Chebyshev's inequality, $P(\sum_{i=1}^k X_i^M \geq p) \geq 1 - 8/\log k \geq \frac{1}{2}$ for all $k$ large enough, and then $REV(\sum_{i=1}^k X_i )\geq p\cdot \frac{1}{2} = k \log k / 4$.
\subsection{Bundled mechanism}
\subsubsection{Different distribution}
Take a large number $N$, we define $F_i$ with $P(M^i) = M^{-i}$ and the rest density at $0$. Then $REV(F^i) = 1$
and so $SREV(\mathcal{F}) = k$, while $BREV(\mathcal{F})$ is at most $\max_i M^i \cdot (M^{-i} + \cdots + M^{-k})$, this obtains a fraction of upper bound of the lower bound $\frac{1}{k} + \epsilon$

\subsubsection{Identical distribution}
For two items, we give the following example:

Let $F$ have support $\{0,1\}$ with $P(1) = \frac{2}{3}$, then $REV(F) = \frac{2}{3}$ while $BREV(F \times F) = \frac{8}{9}$

For more than two items, we provide the following example:

For every $k$ large enough, we provide a one-dimensional distribution $F$ as follows such that $BREV(F^{\times k}) / SREV(F^{\times k}) \leq 0.57$:

The distribution $F$ will be distributed on $\{0,1\}$, with $P(1) = \frac{c}{k}$ where $c = 1.256\ldots$ is the solution of $1-e^{-c} = 2(1-(c+1)e^{-c})$, so the revenue from selling a single item is $\frac{c}{k}$. The bundling auction should clearly offer an integral price. If it offers price $1$ then the probability of selling is $1 - (1 - \frac{c}{k})^k \approx 1 - e^{-c} = 0.715\ldots$, which is also the expected revenue. If it offers price $2$ then the probability of selling is $1 - (1-\frac{c}{k})^k - k(\frac{c}{k})(1-\frac{c}{k})^{k-1} \approx 1 - (c+1)e^{-c}$ and the revenue is twice that, again $0.715\ldots$ If it offers price $3$ then the probability of selling is $1-(1-\frac{c}{k})^k - k(\frac{c}{k})(1-\frac{c}{k})^{k-1} - \binom{k}{2}(\frac{c}{k})^2(1-\frac{c}{k})^{k-2} \approx 1 - (1+c + c^2)e^{-c} \approx 0.13\ldots$, and the revenue is three times higher, which is less than $0.715$. For higher integral prices $t$ the probability of selling is bounded from above by $\frac{c^t}{t!}$, the revenue is $t$ times that, and is even smaller. Thus $BREV(F^{\times k})/SREV(F^{\times k}) \approx 0.715/1.256 \leq 0.57$. In this way, we obtain an upper bound of lower bound with $0.57$ in identical. distribution case.
\section{Summary of this chapter}
In this chapter, we made a study on how much can simple auction mechanisms approximate the optimal revenue. The two simple auction mechanisms studied on this chapter are to sell the items separately, and to sell all items together as a whole bundle. We made a study on the fraction that the simple auction method obtain compared with the optimal auction mechanisms.
